/*
 * BST.cpp
 *
 *  Created on: Jan 30, 2012
 *      Author: beebe
 */

#include "Index.h"
#include <assert.h>
//!  No-arg constructor.  Initializes an empty BST
Index::Index():root(NULL),size(0){}
Index::~Index(){
	Clear();
}


IndexNode * Index::GetRoot()const{
	return root;
}

bool Index::IsEmpty() const{
	return (size ==0);
}

void Index::Clear(){
	Clear(root);
	root = NULL;
}
void Index::Clear(IndexNode * node){
	if (node == NULL)
			return;
	Clear(node->left);
	Clear(node->right);

	delete node;
	size--;
}
int Index::GetSize() const{
	return size;
}

//!  Inserts value v into the BST
//!
//!  @param v The new value being inserted
//!
//!  @return a pointer to the newly inserted node, or NULL if v was already
//!          in the tree (i.e., NULL is used to indicate a duplicate insertion)
IndexNode * Index::Insert(const std::string & word, const std::string & url){
	IndexNode * current = root;
	IndexNode * newnode = new IndexNode(BST(),word);
	newnode->value.Insert(url);
	if(current==NULL){
		root = newnode;
		size++;
	}
	else while(current != NULL){
		if (word.compare(current->word)>0){
			if(current->GetRight() != NULL)
				current = current->GetRight();
			else{
				size++;
				current->right = newnode;
				return newnode;
			}
		} else if (word.compare(current->word)<0){
			if(current->GetLeft() != NULL){
				current = current->GetLeft();
			}else{
				size++;
				current->left = newnode;
				return newnode;
			}
		} else if (word.compare(current->word)==0){
			delete(newnode);
			current->value.Insert(url);
			return NULL;
		}
	}
	return NULL;
}

//!  Searches the tree for value v
//!
//!  @param v The new value being searched for
//!
//!  @return a pointer to the node containing v, or NULL if v is not in the tree
IndexNode * Index::Find(const std::string & v) const{
	IndexNode * current = root;
	while(current != NULL){
		if (v.compare(current->word)>0)
			current = current->GetRight();
		else if (v.compare(current->word)<0)
			current = current->GetLeft();
		else if (v.compare(current->word)==0)
			return current;
	}
	return NULL;
}

std::string Index::toXmlString(){
	std::string xmlOut = "<index>";
	xmlOut += toXmlString(*this->root);
	xmlOut += "</index>";
	return xmlOut;
}
std::string Index::toXmlString(IndexNode & current){
	std::string xmlOut = "";
	if(&current == NULL)
		return "";
	xmlOut += toXmlString(*current.left);
	xmlOut += "<word><value>"+current.word+"</value>"+current.value.toXmlString(*current.value.GetRoot())+"</word>";
	xmlOut += toXmlString(*current.right);
	return xmlOut;
}
